---
title: "棋子换位"
created: 2025-11-28
tags:
  - 算法
---

# 棋子换位

## 题目 [棋子换位](https://www.lanqiao.cn/paper/3863/problem/433/)

![[image-473a6ba0.png]]

## 思路分析

![[image-5dc07b4f.png]]

![[image-f085e62a.png]]

果然内含玄机 得模拟案例才能找到

跳着走的优先级高于移到相邻位置的优先级，在每一步的移动中，如果某一位满足跳走，那么执行跳走后就直接进行下一个状态的判断；假如该状态下不存在跳走的情况，那么就选择走到相邻位置的走法。需要填空代码的位置显然是如果满足这个条件，则不执行走到相邻位置，不满足这个条件时则移动到相邻的位置。解题的关键就是找出这个判断条件，现在通过手动模拟AAA.BBB的移动过程来发现这个规律。

```
①A②A③A.①B②B③B   //初始状态(前面的数字代表字母的编码)(此状态下无跳走，③A可以右移，①B可以左移，但是先判断③A位置)
①A②A.③A①B②B③B    //此状态下①B满足跳走
①A②A①B③A.②B③B    //此时无跳走，③A可以右移，②B可以左移
```

此时也许可以发现，③A的两侧都是B即相同(PS忽略符号’.’)，②B两侧1A1B即相异

假如选择③A右移即选择相同的移动，则以后的移动状态为（省略字母编码）：

```cpp
AAB.ABB->A.BAABB->AB.AABB->B.AAABB(卡死了)
```

若选择②B左移即选择相异的移动，以后的移动状态为：

```cpp
AABAB.B->AAB.BAB->A.BABAB->.ABABAB->BA.ABAB->BABA.AB
->BABABA.->BABAB.A->BAB.BAA->B.BABAA->BB.ABAA->BBB.AAA
```

即达到所要求目标。

即可猜测所填条件为当可移动位置的左右两侧字母相同时则不选择移动(写代码是要考虑到符号’.’的占位问题)。

所以：

```cpp
if(valid(data,i+dd+dd)&&valid(data,i-dd)&&data[i+dd+dd]==data[i-dd]) continue;  //填空位置
```

## 代码实现

```cpp
#include <stdio.h>

#include <string.h>

void move(char* data, int from, int to)

{

    data[to] = data[from];

    data[from] = '.';

}

int valid(char* data, int k)

{

    if(k<0 || k>=strlen(data)) return 0;

    return 1;

}

void f(char* data)

{

    int i;

    int tag;

    int dd = 0; // 移动方向

    while(1){

        tag = 0;

        for(i=0; i<strlen(data); i++){

            if(data[i]=='.') continue;

            if(data[i]=='A') dd = 1;

            if(data[i]=='B') dd = -1;

            if(valid(data, i+dd) && valid(data,i+dd+dd)

            && data[i+dd]!=data[i] && data[i+dd+dd]=='.'){

            //如果能跳...

                move(data, i, i+dd+dd);

                printf("%s\n", data);

                tag = 1;

                break;

            }

        }

        if(tag) continue;

        for(i=0; i<strlen(data); i++){

            if(data[i]=='.') continue;

            if(data[i]=='A') dd = 1;

            if(data[i]=='B') dd = -1;

            if(valid(data, i+dd) && data[i+dd]=='.'){

            // 如果能移动...

                if(valid(data,i+dd+dd)&&valid(data,i-dd)&&data[i+dd+dd]==data[i-dd]) continue;

                move(data, i, i+dd);

                printf("%s\n", data);

                tag = 1;

                break;

            }

        }

        if(tag==0) break;

    }

}

int main()

{

    char data[] = "AAAA.BBBB";

    f(data);

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[凑平方数|凑平方数]] 🏠 [[00-冲刺国赛]] ➡️ [[机器人塔|机器人塔]]